Análisis de Estructuras de Datos y Algoritmos en Python (2ª edición): Modelado de grafos: del mundo real a estructuras de datos abstractas

图论建模是将现实世界的复杂连接关系（如互联网路由、状态转换）抽象为数学对象 $G = (V, E)$ 的过程。通过将实体定义为vértice (vértice) y definir las relaciones comoarista (arista), lo que nos permite utilizar un tipo de dato abstracto (ADT) y algoritmos uniformes para resolver una amplia variedad de problemas.

Definición de componentes clave

vértice (vértice): también conocido como nodo. Tiene una "clave" (Key) como identificador único y puede contener un "carga útil" (Payload).
arista (arista): conecta dos vértices, indicando que existe una relación entre ellos. Puede ser unidireccional (grafo dirigido) o bidireccional.
peso (peso): el valor en una arista, que representa un costo (como distancia, latencia o ancho de banda).

Precisión matemática

Matemáticamente, $G = (V, E)$. Donde $V$ es el conjunto de vértices y $E$ es el conjunto de aristas formadas por pares ordenados $(v, w)$, con $v, w \in V$. Esta estructura altamente abstracta nos permite resolver desde la navegación en mapas hasta la recomendación en redes sociales utilizando el mismo conjunto de algoritmos BFS/DFS.

Iluminación sobre modelado: grafo del espacio de estados

Al resolver acertijos lógicos (como el problema de los recipientes), cadaestado válidoes un vértice, y cadaoperación válidaes una arista. Resolver el problema consiste en encontrar una ruta desde el vértice inicial hasta el vértice objetivo.

Desafío de modelado lógico: Problema de los recipientes (Tarea de escritura)

Mapear estados lógicos a una estructura de grafo

Tienes dos barriles con capacidades de 4 y 3 galones, sin marcas. Puedes llenarlos con una bomba, vaciarlos o trasvasar agua entre ellos. Tarea: hacer que el barril de 4 galones tenga finalmente 2 galones de agua.

Escribe un programa o describe su lógica de modelado para resolver este problema. (Requisito: salida de al menos 150 palabras en descripción lógica o implementación de código)

Respuesta:
模型方案： 1. 顶点定义：使用元组 (v4, v3) 表示状态，其中 v4 为 4加仑坛子的水量，v3 为 3加仑坛子的水量。初始顶点为 (0,0)，目标顶点为 (2, x)。 2. 边定义：合法的操作（灌满、倒空、转移）构成边。例如 (0,0) -> (4,0) 是“灌满4加仑”的操作。 3. 解决步骤： - (0,0) -> (0,3) : 灌满3加仑 - (0,3) -> (3,0) : 倒入4加仑坛子 - (3,0) -> (3,3) : 再次灌满3加仑 - (3,3) -> (4,2) : 灌满4加仑坛子，此时3加仑坛子剩下2加仑 - (4,2) -> (0,2) : 倒空4加仑坛子 - (0,2) -> (2,0) : 将3加仑坛子中的2加仑倒入4加仑坛子，达成目标。

Modelado de escenarios: Cebra y león cruzando el río (Tarea de escritura)

Búsqueda de rutas bajo condiciones de restricción

Tres cebras y tres leones están listos para cruzar el río. El bote tiene capacidad para 2. Si en cualquier orilla el número de leones supera al de cebras, las cebras serán devoradas. Encuentra un método seguro para cruzar el río.

Describe el método de modelado del grafo para este problema y una ruta viable. (Requisito: salida de al menos 120 palabras)

Respuesta:
建模逻辑： 1. 状态表示：(A_left, L_left, boat_pos)，分别代表左岸羚羊数、狮子数和船的位置（0左1右）。 2. 约束条件：A_left == 0 或 A_left >= L_left，且右岸同样满足此条件。 3. 路径序列： - (3,3,0) -> (3,1,1) : 运2狮子到右岸 - (3,1,1) -> (3,2,0) : 回1狮子 - (3,2,0) -> (3,0,1) : 运剩下2狮子到右岸 - (3,0,1) -> (3,1,0) : 回1狮子 - (3,1,0) -> (1,1,1) : 运2羚羊到右岸 - (1,1,1) -> (2,2,0) : 回1羚羊1狮子 - (2,2,0) -> (0,2,1) : 运最后2羚羊到右岸 - (0,2,1) -> (0,3,0) : 回1狮子 - (0,3,0) -> (0,1,1) : 运2狮子到右岸 - (0,1,1) -> (0,2,0) : 回1狮子 - (0,2,0) -> (0,0,1) : 全员到达右岸。

Análisis de complejidad y estructura (Respuesta breve)

Fundamentos teóricos de algoritmos

分析 buildGraph 函数（根据代码清单 7-2）的时间复杂度。

Respuesta:
La complejidad temporal de buildGraph es O(V + E). Donde V es el número de vértices y E es el número de aristas (o relaciones entre palabras). La operación addVertex es O(1), y la operación addEdge implica búsqueda en diccionario, también promediando O(1), por lo tanto el tiempo total es lineal respecto al tamaño de entrada.

Dibuja la estructura de grafo correspondiente a la siguiente matriz de adyacencia: A-B:7, A-C:5, A-F:1, B-D:7, B-E:3, C-B:2, C-F:8, D-E:2, E-D:5, F-C:1.

Respuesta:
Descripción de la estructura de grafo: - Conjunto de nodos V = {A, B, C, D, E, F} - Conjunto de aristas dirigidas con peso E = { (A,B,7), (A,C,5), (A,F,1), (B,D,7), (B,E,3), (C,B,2), (C,F,8), (D,E,2), (E,D,5), (F,C,1) } Este es un grafo dirigido, cíclico y ponderado complejo.